\chapter{Вопрос № 17}

Задача о марках и бандероли в случае, когда порядок наклейки марок не важен - рекуррентное соотношение, решение с помощью обыкновеннх производящих функций. Обобщения задачи. Задача о разбиение числа $n$ на слагаемые. Простейшие свойства количества $p\left(n\right)$ таких разбиений.

\section{Задача о марках и бандероли}

Требуется отправить бандероль, для этого на нее необходимо наклеить марок на 18 рублей. На почте имеются марки достоинством в 4, 6 и 10 рублей. Сколькими способами можно это сделать, если наклейки отличающиеся только порядком наклейки марок не различмы?

Допустим для начала, что сумма на которую нужно наклеить марок не 18 рублей, а произвольное число $n$ рублей, с учетом этого наша задача сводится к решению уравнения $$ 4 y_4 + 6 y_6 + 10 y_{10} = n $$ в целых неотрицательных числах.

\subsection{Рекуррентное соотношение}

Обозначим через $\Phi\left(n;4,6,10\right)$ число способов наклейки марок на сумму $n$ рублей используя марки достоинством 4, 6 или 10 рублей. Тогда можно сфомулировать систему рекуррентных соотношений:
\begin{equation}
	\begin{split}
		& \Phi\left(n;4,6,10\right) = \Phi\left(n-10;4,6,10\right) + \Phi\left(n;4,6\right) \\
		& \Phi\left(n;4,6\right) = \Phi\left(n-6;4,6\right) + \Phi\left(n;4\right) \\
		& \Phi\left(n;4\right) = \Phi\left(n-4;4\right) \\
		& \Phi\left(0;...\right) = 1 \\
		& \Phi\left(<0; ...\right) = 0
	\end{split}
\end{equation}
всю систему можно собрать в одно рекуррентное соотношение с начальными условиями, и в каждом конкретном случае оно даст способ вычисления требуемого значений, но не даст замкнутой формулы.

\subsection{Решение через опф}

Рассмотрим опф следующего вида:
\[
	f\left(x\right) = \left(1 + x^4 + x^8 + ...\right)\left(1 + x^6 + x^{12} + ...\right)\left(1 + x^{10} + x^{20} + ...\right)
\]
если перемножать скобки, то будем получать слагаемые следующего вида:
\[
	x^{4k_1 + 6k_2 + 10k_3}
\]
суммируя все слагаемые с равными степенями $x$ получаем как раз количество целочисленных неторицательных решений уравнения:
\[
	4y_1 + 6y_2 + 10y_3 = n
\]
а это как раз то что нам нужно. Этот подход естественным образом расширается на произвольные номиналы марок, а также на различные ограничения, например, если ни одна марка не должна повторяться, тогда получаем следующий результат:
\[
	f\left(x\right) = \left(1+x^4\right)\left(1+x^6\right)\left(1+x^{10}\right)
\]

\section{Разбиение числа $n$ на слагаемые}

Как уже отмечалось, задача о марках сводится к задаче о количестве разбиений числа $n$ на слагаемые. Теперь решим задачу о разбиении произвольного числа $n$ без ограничений на слагаемые и на их число. Количество таких разбиений обозначается как $p\left(n\right)$.

Для чисел $p\left(n\right)$ справедливы несколько очевидных свойств:
\begin{enumerate}
\item $p\left(1\right) = 1$

\item $p\left(2\right) = 2$

\item $p\left(3\right) = 3$

\item $p\left(4\right) = 5$

\item $p\left(5\right) = 7$
\end{enumerate}

опф описывающая числа $p\left(n\right)$ выглядит следующим образом:
\begin{equation}
	\begin{split}
		& f\left(x\right) = \left(1+x+x^2+...\right)\left(1+x^2+x^4+...\right)\left(1+x^3+x^6+..\right) ... = \\
		& = \prod_{i=1}^\infty \frac{1}{1-x^i}
	\end{split}
\end{equation}
но так как разбить число $n$ на слогаемые, которые больше самого числа очевидно не возможно, то можно урезать производящую функцию до следующейго вида:
\begin{equation}
	f\left(x\right) = \prod_{i=1}^n\frac{1}{1-x^i}
\end{equation}
